package leetcode;

import java.util.HashSet;
import java.util.Set;

import org.junit.Test;

public class StrStr {
	public int strStrPos(String haystack, String needle) {
		if (haystack == null || needle == null)
			return -1;

		Set<Integer> matches = new HashSet<Integer>();
		Set<Integer> remove = new HashSet<Integer>();
		int len = haystack.length();
		for (int p = 0; p < len; ++p) {
			remove.clear();
			for (Integer mp : matches) {
				int offset = p - mp;
				if (offset >= needle.length())
					return mp;
				if (needle.charAt(offset) != haystack.charAt(p))
					remove.add(mp);
			}
			matches.removeAll(remove);

			if ((needle.isEmpty() || needle.charAt(0) == haystack.charAt(p)) && p+needle.length() <= len)
				matches.add(p);
		}

		if (matches.isEmpty())
			return -1;

		int min = len;
		for (Integer mp : matches) {
			if (mp < min && mp + needle.length() <= len)
				min = mp;
		}

		
		return min == len? -1 : min;
	}

	public String strStr(String haystack, String needle) {
		int idx = strStrPos(haystack, needle);
		if (idx == -1) {
			if (haystack.isEmpty() && needle.isEmpty())
				return "";
			else
				return null;
		} else
			return haystack.substring(idx);
	}
	
	public String strStr2(String haystack, String needle) {
        if (haystack == null || needle == null)
            return null;
            
        if (needle.isEmpty())
            return haystack;
        
        for (int i=0; i< haystack.length() - needle.length()+1; ++i){
            if (isMatch(haystack, needle, i))
                return haystack.substring(i);
        }
        
        return null;
    }
    
    public boolean isMatch(String haystack, String needle, int p){
        int offset = p;
        
        while (p-offset<needle.length()){
            if (haystack.charAt(p) != needle.charAt(p-offset))
                return false;
                
            ++p;
        }
        
        return true;
    }

	@Test
	public void testStrStr() {
		StrStr s = new StrStr();
		System.out.println(s.strStr2("aaa", "a"));
		//System.out.println(s.strStr2("", ""));
		//System.out.println(s.strStr2("a", ""));
		//System.out.println(s.strStr2("mississippi", "issip"));
	}
}